open Data

let time_ref = Sys.time ()

type solution_t = {
  plans: int array array;
  times: int array;
  cost: int
}

let insertion_cost = fun k t p i ->
  time.(k).(p.(i-1)).(t) + time.(k).(t).(p.(i)) - time.(k).(p.(i-1)).(p.(i))



let insertion = fun t p i ->
  let rec insertion = fun t p i ->
    if i = 0
    then t :: p
    else List.hd p :: insertion t (List.tl p) (i-1)
  in Array.of_list (insertion t (Array.to_list p) i)

let best_insertion = fun t plans k ->
  let lower_cost = ref max_int
  and position = ref (-1) in

    for i=1 to Array.length plans.(k) -1 do
      let ic = insertion_cost k t plans.(k) i in
		if ic < !lower_cost then
		  begin
		    lower_cost := ic;
		    position := i
		  end
    done;
    plans.(k) <- insertion t plans.(k) !position

let plan_cost = fun plans k ->
  let c = ref 0 in
  for i=1 to Array.length plans.(k) -1 do
    c:= !c + time.(k).(plans.(k).(i-1)).(plans.(k).(i))
  done;
    !c

let select_from_list = fun l -> List.nth l (Random.int (List.length l))

let forward_search = fun tasks ->
  let ball = Array.init m (fun _ -> 1) in
  let plans = Array.init m (fun i -> [|n+2*i; n+2*i+1|] ) in
  let available_machine_for_task = fun t ->
    let l = Array.to_list (Array.init m (fun i -> i)) in
      if ttype.(t) = Dr
      then List.filter (fun i -> ball.(i)>0) l
      else l
  in
  
  let rec forward_search = fun tasks plans ->
    match tasks with
      | [] -> plans
      | t::tasks_list ->

	  let machines = available_machine_for_task t in
	  let machine = select_from_list machines in
	    best_insertion t plans machine;
	    if ttype.(t) = Dr then ball.(machine) <- ball.(machine) -1; 
	    forward_search tasks_list plans
  in forward_search tasks plans

let large_search = fun plans balls ->
  let pendings = ref [] in
  let remove_node = fun plans balls ->
    let available_machines = 
      List.filter 
	(fun i -> Array.length plans.(i) > 2) 
	(Array.to_list (Array.init m (fun i -> i))) in
    let machine = select_from_list available_machines in
    let selected_task = 
      plans.(machine).(Random.int (Array.length plans.(machine) -2) +1) in 
      pendings := selected_task :: !pendings;
      plans.(machine) <- Array.of_list 
	(List.filter (fun x -> x<>selected_task) (Array.to_list plans.(machine)));
      if ttype.(selected_task) = Dr then balls.(machine) <- balls.(machine) +1
  in
  let rec insertion = fun pendings plans balls ->
  let available_machine_for_task = fun t ->
    let l = Array.to_list (Array.init m (fun i -> i)) in
      if ttype.(t) = Dr
      then List.filter (fun i -> balls.(i)>0) l
      else l
  in
    match pendings with
      | [] -> ()
      | t::other_pendings ->
	  let machines = available_machine_for_task t in
	  let machine = select_from_list machines in
	    best_insertion t plans machine;
	    if ttype.(t) = Dr then balls.(machine) <- balls.(machine) - 1;
	    insertion other_pendings  plans balls
  in ()



let print_solution = fun s ->
  Printf.printf "%04.2f\t%d\t\t" (Sys.time() -. time_ref) s.cost;
  Array.iter (fun c -> Printf.printf "%d \t" c) s.times;
  print_newline();;
  
    




let _ = 
  ignore (Random.self_init());
  if Array.length Sys.argv < 3 
  then Printf.printf "Too few arguments"
  else
    begin
      let pendings = Array.to_list (Array.init n (fun i -> i)) in
      let current_solution = 
	let s = forward_search pendings in
	let t = Array.init m (fun i -> plan_cost s i) in
	 ref { plans = s; times = t; cost = Utils.max_array t }
      in
	print_solution !current_solution;
	while true do
	  let new_solution = forward_search pendings in
	  let new_costs = Array.init m (fun i -> plan_cost new_solution i) in
	  let cost = Utils.max_array new_costs in
	    if  cost < !current_solution.cost then
	      begin
		current_solution := 
		  { plans = new_solution; times = new_costs; cost = cost };
		print_solution !current_solution;
	      end
	      
	done
    end;;
    
